package com.company;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 5.榨汁计划(22分)
 *
 *  <ul>
 *  <li>问题描述:
 *  <br>有一堆水果，里面混有苹果和梨子;有2台榨汁机。已知每个水果的重量,
 *  以及每榨50克同类水果所需要的时间（秒)，问如何安排使得将所有水果榨成汁的时间最短。
 *
 *  <li>要求:
 *  <ul><li>完成题目对应的程序模板（FruitJuicing）中的方法:
 *  int minJuicingTime(int appleJuicingCostTime，int[] appleWeights,int
 *  pearJuicingCostTime，int[] pearWeights);
 * <li>该方法的入口参数appleJuicingCostTime为每榨50克苹果所需时间，appleWeights
 * 为需要榨汁的苹果重量数组，pearJuicingCostTime为每榨50克梨子所需时间，pearWeights
 * 为需要榨汁的梨子重量数组;
 * <li>最后输出结果为把所有水果全部榨成果汁所用的最短时长（秒）。
 * <li>提示:每个水果的重量肯定能被50所整除</ul>
 *
 * <li>样例:
 * <ul><li>样例1
 * <br>输入:
 * <blockquote>
 *  appleJuicingCostTime = 3
 *  <br>appleWeights = [100,300]
 *  <br>pearJuicingCostTime = 2
 *  <br>pearWeights = [200,150]
 * </blockquote>
 * 输出: 20
 * <br>解释: 第一个榨汁机榨苹果[100]和梨子[200,150],第二个榨汁机榨苹果[300]，第一个榨汁机总耗时20秒，第二个榨汁机耗时18秒，所以结果输出20。
 * </ul>
 * </ul>
 *
 * @author jianf
 * @date 2021年09月09 16:05
 */
public class FruitJuicing {

    int minJuicingTime(int appleJucingCostTime, int[] appleWeights,
                       int pearJuicingCostTime, int[] pearWeights) {
        int[] timeList = deal(appleJucingCostTime, appleWeights, pearJuicingCostTime, pearWeights);
        //最小用时的范围，一定是： 大于等于 最费时的水果 且小于 所有水果的用时之和
        int low = timeList[0];
        int hight = Arrays.stream(timeList).sum();
        //采用二分查找法，将上面的时间逐步缩小，直到找最小用时的范围
        while (low < hight){
            //除以2
            int mid = (low+ hight) >>1;
            if(backTrace(timeList,new int[2],0,mid)){
                hight = mid;
            }else {
                low = mid +1;
            }
        }
        return low;
    }

    /**
     * 转换为统一的时间数组并排序
     */
    int[] deal(int appleJucingCostTime, int[] appleWeights,
                       int pearJuicingCostTime, int[] pearWeights) {
       Integer[] res = new Integer[appleWeights.length + pearWeights.length];

       for (int i = 0; i < appleWeights.length; i++) {
           res[i] = appleWeights[i] / 50 * appleJucingCostTime;
        }
        for (int i = 0; i < pearWeights.length; i++) {
            res[appleWeights.length + i] =pearWeights[i] / 50 * pearJuicingCostTime;
        }

        System.out.println("水果时间："+Arrays.toString(res));
        return Arrays.stream(res).sorted(Collections.reverseOrder())
                .mapToInt(Integer::valueOf).toArray();
    }

    /**
     * 该缩小二分查找的上下限，下限为所有工作中的最大工作量，上限为所有工作的工作量之和。
     * 每一个工作都必须被分配，因此必然有一个工人承接了工作量最大的工作；
     * 在最坏情况下，只有一个工人，他必须承接所有工作。
     * 优先分配工作量大的工作。
     * 感性地理解，如果要求将小石子和大石块放入玻璃瓶中，优先放入大石块更容易使得工作变得简单。
     * 在搜索过程中，优先分配工作量小的工作会使得工作量大的工作更有可能最后无法被分配。
     * 当工人 ii 还没被分配工作时，我们不给工人 i+1i+1 分配工作。
     * 如果当前工人 ii 和 i+1i+1 都没有被分配工作，那么我们将工作先分配给任何一个人都没有区别，如果分配给工人 ii 不能成功完成分配任务，那么分配给工人 i+1i+1 也一样无法完成。
     * 当我们将工作 ii 分配给工人 jj，使得工人 jj 的工作量恰好达到 \textit{limit}limit，且计算分配下一个工作的递归函数返回了 \text{false}false，此时即无需尝试将工作 ii 分配给其他工人，直接返回 \text{false}false 即可。
     * 常规逻辑下，递归函数返回了 \text{false}false，那么我们需要尝试将工作 ii 分配给其他工人，假设分配给了工人 j'j
     * ′
     *  ，那么此时工人 j'j
     * ′
     *   的工作量必定不多于工人 jj 的工作量；
     * 如果存在一个方案使得分配给工人 j'j
     *   能够成功完成分配任务，那么此时必然有一个或一组工作 i'i
     *   取代了工作 ii 被分配给工人 jj，否则我们可以直接将工作 ii 移交给工人 jj，仍然能成功完成分配任务。而我们知道工作 i'i
     *   的总工作量不会超过工作 ii，因此我们可以直接交换工作 ii 与工作
     *  ，仍然能成功完成分配任务。这与假设不符，可知不存在这样一个满足条件的工人j'
     *
     * @param frutList 各水果加工所用工时列表，正序排列之后的
     * @param juics    榨汁机
     * @param i        当前要处榨的水果ind
     * @param limit    规定的最长完成时间
     * @return 是否能在规定的时限内完成
     */
    boolean backTrace(int[] frutList, int[] juics, int i, int limit) {
        //如果已经到了最后一个，则直接返回成功，并结束
        if (i >= frutList.length) {
            return true;
        }
        int cur = frutList[i];
        for (int j = 0; j < juics.length; j++) {
            //如果被分配的榨汁机工作量juics[j]与当前的工作量cur之和不超过limit 的限制
            //则分配给该机器来榨
            if (juics[j] + cur <= limit) {
                juics[j] += cur;
                //再计算下一个水果的情况
                if (backTrace(frutList, juics, i + 1, limit)) {
                    return true;
                }
                juics[j] -= cur;
            }
            // 如果当前榨汁机被分配工作，那么下一个榨汁机也必然未被分配工作
            // 或者当前水果恰能使该榨汁机的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (juics[j] == 0 || juics[j] + cur == limit) {
                break;

            }
        }

        return false;
    }

    public static void main(String[] args) {
        int appleJucingCostTime = 3;
        int[] appleWeights = {100, 300};
        int pearJuicingCostTime = 2;
        int[] pearWeights = {200, 150};
        FruitJuicing c = new FruitJuicing();
        System.out.println("\n最小时间 = " + c.minJuicingTime(appleJucingCostTime, appleWeights, pearJuicingCostTime, pearWeights));

    }
}
